216. 组合总和 III

Similar Question

Solution Tips

方案一: 回溯 - N 叉树思路

var combinationSum3 = function(k, n) {
    // 感觉也是一道典型的回溯题
    // 但是和 x 数之和有一丢丢像? 但是是动态的, 所以不太好设置对撞指针
    // 只能作为剪枝的考虑
    const res = [];
    const cur = [];
    let curSum = 0;

    function backTracking(curIndex) {
        if (cur.length === k) {
            if (curSum === n) {
                res.push([...cur])
            }
            return;
        }

        // 根据 curSum 和 curLen 进行剪枝
        // n - curSum 等于剩余的值之和, rest / (k - curLen), 剩余值的平均值
        const rest = n - curSum;
        const restAverage = rest / (k - cur.length);
        const max = restAverage <= 9 ? restAverage : 9;
        for (let i = curIndex; i <= max; i++) {
            cur.push(i);
            curSum += i;
            backTracking(i + 1);
            // 回溯操作
            cur.pop();
            curSum -= i;
        }
    }

    backTracking(1);
    return res;
};

方案二: 回溯 - 二元思路

var combinationSum3 = function(k, n) {
    const temp = [];
    const res = [];
    const dfs = (cur, n, k, sum, res) => {
        if (temp.length + (n - cur + 1) < k || temp.length > k) {
            return;
        }        
        if (temp.length === k && temp.reduce((previous, value) => previous + value, 0) === sum) {
            res.push(temp.slice());
            return;
        }
        temp.push(cur);
        dfs(cur + 1, n, k, sum, res);
        temp.pop();
        dfs(cur + 1, n, k, sum, res);
    }

    dfs(1, 9, k, n, res);
    return res;
};

方案三: 子集枚举 - 二进制枚举思路

Loading Question... - 力扣（LeetCode）